//
// Created by wangxiyue on 2019/9/24.
//
#include <stdio.h>

int LENGTH = 5;

void print(int *a, int low, int high) {
    for (int i = low; i <= high; i++) {
        printf("%d\t", a[i]);
    }
    printf("\n");
}

void merge(int *a, int low, int high, int mid) {
    int temp_arr_length = high - low + 1;

    int t[temp_arr_length];

    int j = mid + 1;
    int i = low;
    int m = 0;
    for (; i <= mid && j <= high;) {
        t[m++] = a[i] < a[j] ? a[i++] : a[j++];
    }

    while (j <= high) {
        t[m++] = a[j++];
    }

    while (i <= mid) {
        t[m++] = a[i++];
    }

    for (int i = 0; i < m; i++) {
        a[low + i] = t[i];
    }
    printf("\n 并: ");
    print(a, low, high);
}

void merge_sort(int *a, int low, int high) {

    if (low >= high) {
        return;
    }

    int mid = (low + high) >> 1;
    printf("\n 归:");
    print(a, low, high);
    merge_sort(a, low, mid);
    merge_sort(a, mid + 1, high);
    merge(a, low, high, mid);
}


int main() {

    int a[] = {5, 1, 3, 2, 4, 0};
    merge_sort(a, 0, 5);
    printf("\n 排序完成:");
    print(a, 0, 5);
    return 0;
}

